﻿#pragma once
#include "Index.h"
class ILongestPalindromeSubStr
{
public:
	/**
	 * 最长回文子串.
	 * https://leetcode.cn/problems/longest-palindromic-substring
	 * 给你一个字符串 s，找到 s 中最长的回文子串。
	 *
	 * 示例 1：
	 * 输入：s = "babad"
	 * 输出："bab"
	 * 解释："aba" 同样是符合题意的答案。
	 *
	 * 示例 2：
	 * 输入：s = "cbbd"
	 * 输出："bb"
	 */
	virtual std::string longestPalindrome(std::string s) = 0;
};
class LongestPalindromeSubStr
{
public:
	/**
	 * 暴力解法.
	 * 时间:O(n^3) 空间:O(1)
     */
	class Brute:public ILongestPalindromeSubStr
	{
	public:
		
		std::string longestPalindrome(std::string s) override
		{
			if (s.empty())
				return "";
			const int strSize = s.size();

			int longestLeft = 0, longestRight = 0;

			//以[i..j]为边界的子串
			for (int i = 0; i < strSize - 1; ++i)
				for (int j = i + 1; j < strSize; ++j)
				{
					if (isPalindrome(s, i, j) && (j - i) > (longestRight - longestLeft))
					{
						longestLeft = i;
						longestRight = j;
					}
				}

			return s.substr(longestLeft, longestRight - longestLeft + 1);
		}
	private:
		//判断字符在[left,right]的部分是否为回文串?
		bool isPalindrome(const std::string& s,int left,int right)
		{
			if (s.empty() || left > right)
				return false;
			const int size = right - left + 1;
			for (int i = 0; i < size; ++i)
			{
				if (s[left] != s[right])
					return false;
				left++;
				right--;
			}
			return true;
		}
	};

	/**
     * 中心扩散法.
     * 时间:O(n^2) 空间:O(1)
     *
	 * 遍历字符串，尝试将遍历到的字符作为回文子串的中心，往两边扩散找到最大的长度.
	 * 回文子串的扩散分为长度为奇数和长度为偶数的两种情况.
	 * 从每次的扩散结果中更新最长的回文子串结果.
	 */
	class CenterSpeard:public ILongestPalindromeSubStr
	{
	public:
		std::string longestPalindrome(std::string s) override
		{
			if (s.empty())
				return "";
			const int strSize = s.size();

			int longestLeft = 0, longestRight = 0;
			for (int i = 0; i < strSize - 1; ++i)
			{
				//以s[i]为中心的奇数最长回文子串
				int left = i, right = i;
				while (left >= 0 && right < strSize && s[left] == s[right])
				{
					left--;
					right++;
				}
				//回到while退出前的合法边界
				left++;
				right--;
				if ((right - left) > (longestRight - longestLeft))
				{
					longestLeft = left;
					longestRight = right;
				}


				//以s[i],s[i+1]为中心的偶数最长回文子串
				left = i, right = i + 1;
				while (left >= 0 && right < strSize && s[left] == s[right])
				{
					left--;
					right++;
				}
				//回到while退出前的合法边界
				left++;
				right--;
				if ((right - left) > (longestRight - longestLeft))
				{
					longestLeft = left;
					longestRight = right;
				}
			}

			return s.substr(longestLeft, longestRight - longestLeft + 1);
		}
	};

	/**
	 * 动态规划.
	 *
	 * 设dp[i][j](bool)表示字符串在区间[i..j]是否回文串，那么状态转移方程为:
	 *
	 *	dp[i][j]= false,当s[i]!=s[j]
	 *	dp[i][j]= dp[i+1][j-1],当s[i]==s[j]时，回文串的判定取决于内部是否为回文串
	 *
	 *	时间:O(n^2) 空间:O(n)
	 */
	class DP:public ILongestPalindromeSubStr
	{
	public:
		std::string longestPalindrome(std::string s) override
		{
			if (s.empty())
				return "";

			const int strSize = s.size();
			int longestLeft = 0, longestRight = 0;

			//列表示的是子串的right，行表示的是子串的left
			//2列DP交替
			std::vector<bool> dp[2] = { std::vector<bool>(strSize,false),std::vector<bool>(strSize,false) };

			//一列一列地填
			for (int col = 0; col < strSize; ++col)
			{
				std::vector<bool>& lastDp = dp[(col + 1) % 2];
				std::vector<bool>& curDp = dp[col % 2];

				for (int row = col; row >= 0; --row)
				{
					const int left = row;
					const int right = col;

					curDp[left] = false;
					if (s[left] == s[right])
					{
						if (right - left <= 1)//left和right之间没有更小的回文串需要判断
							curDp[left] = true;
						else
							curDp[left] = lastDp[left + 1];
					}

					//当left到right为回文子串，尝试更新最长回文子串
					if (curDp[left] && (right - left) > (longestRight - longestLeft))
					{
						longestLeft = left;
						longestRight = right;
					}
				}
			}

			return s.substr(longestLeft, longestRight - longestLeft + 1);
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class LongestPalindromeSubStrTest :public SolutionTestor<ILongestPalindromeSubStr>
{
protected:
	void LoadSolutions(std::vector<ILongestPalindromeSubStr*>& solutions) override
	{
		solutions = {
			new LongestPalindromeSubStr::Brute,
			new LongestPalindromeSubStr::CenterSpeard,
			new LongestPalindromeSubStr::DP,
		};
	}
};
TEST_F(LongestPalindromeSubStrTest, longestPalindrome)
{
	TestForSolutions([](ILongestPalindromeSubStr* solution)
		{
			std::vector<std::tuple< std::string,int>> testCases = {
				std::make_tuple("",0),
				std::make_tuple("babad",3),
				std::make_tuple("cbbd",2),
				std::make_tuple("a",1),
				std::make_tuple("aaaaaaa",7),
				std::make_tuple("dffeeabbbaeefaabbbababa",11),
				std::make_tuple("bananas",5)
			};

			for(auto& testCase :testCases)
			{
				const auto& input = std::get<0>(testCase);

				auto result=solution->longestPalindrome(input);

				if (input.empty())
					EXPECT_TRUE(result.empty());
				else
				{
					const int longestLen = std::get<1>(testCase);
					Json::Value failedJval;
					failedJval["input"] = input;
					failedJval["result"] = result;
					failedJval["longestLen"] = longestLen;
					Json::StyledWriter jwriter;
					const std::string failedMsg = jwriter.write(failedJval);

					//result是input的字符
					EXPECT_TRUE(input.find(result) != std::string::npos) << failedMsg;
					//result是回文的
					auto reversedResult = result;
					std::reverse(reversedResult.begin(), reversedResult.end());
					EXPECT_EQ(result, reversedResult) << failedMsg;
					//result是回文子串长度最长的
					EXPECT_EQ(result.size(), longestLen) << failedMsg;
				}
			}
		});
}
#endif